It is often desirable to compress data in order to reduce the consumption of storage resources and/or transmission overhead. Through the use of lossless compression techniques, it is possible to compress and decompress the data exactly, without any loss of information during the compression/decompression process.
Generally, there is a tradeoff between the compression ratio and the processing performance achieved when performing the compression and decompression. The term “compression ratio” commonly denotes a measure of the effectiveness of the compression, and is widely defined as the percentage of the original data volume that has been eliminated by the compression. The more effective compression is, the higher the compression ratio. The term “performance” herein denotes a measure of the ability of a system or device to complete the execution of compression/decompression algorithms within a given amount of time and utilizing a given amount of general computational resources. The faster a system or device can complete the execution of compression/decompression algorithms, and the less interference such execution has with other computational tasks, the higher is the performance. It is well-known that, to increase the compression ratio (if it is possible to do so), it is necessary to perform additional processing on the data, both during the compression phase and the decompression phase.
Presently, one of the most popular lossless data compression/decompression algorithms in use is the well-known Lempel-Ziv 1977 algorithm (herein denoted as “Lempel-Ziv”), which compresses data by replacing repeated data patterns with compact bounded vector references to earlier occurrences. In the present application, the Lempel-Ziv data compression algorithm and the related Lempel-Ziv-Huffman algorithm are used as examples of data compression algorithms for describing embodiments of the present invention, and to illustrate how the present invention overcomes limitations of the prior art. It is understood, however, that the present invention is not limited to the use of Lempel-Ziv algorithms, and that other data compression algorithms may also be employed in various embodiments of the present invention.
Lempel-Ziv compression requires only a single pass through the data for both compression and decompression, and therefore it is easy to attain good performance with Lempel-Ziv. Lempel-Ziv alone, however, does not achieve optimum compression ratios. Further compression is possible by following a primary Lempel-Ziv compression stage with a secondary compression stage that selectively utilizes the Huffman encoding algorithm, as detailed in the DEFLATE Compressed Data Format Specification Version 1.3, RFC 1951—May 1996 (herein denoted as “RFC 1951”), which is incorporated by reference for all purposes as if set forth fully herein. This compound algorithm, as well as the data compression results obtained thereby are herein denoted as “Lempel-Ziv-Huffman”. The secondary compression stage is herein characterized as “selectively” utilizing Huffman encoding because not all the compressed output data from the primary Lempel-Ziv compression stage is Huffman-encoded: certain portions of the tokens output from Lempel-Ziv are not processed by explicit Huffman encoding in the secondary stage. The term “token” herein denotes a data element which is utilized for the reconstruction of the original data prior to compression; Lempel-Ziv tokens carry information about the original data, and the compressed output from the Lempel-Ziv lossless data compression process can be viewed as a token series which uniquely specifies the original data but which is more compact than the original data. Lempel-Ziv tokens are of variable length and, as used herein, the term “token” referring to Lempel-Ziv compressed data denotes a data element specifying one of the following, in accordance with RFC 1951:
(a) a literal byte data value;
(b) the length, in bytes, of a repeated data pattern; or
(c) the backward distance, in bytes, of a repeated data pattern, measured with respect to the token's position.
It is important to note that, when decompressing compressed data, the decompression stages are applied in reverse order from the compression process. For Lempel-Ziv-Huffman, the decompression operates first on the compressed data by selectively utilizing explicit Huffman decoding, after which a Lempel-Ziv decompression stage operates.
It is also important to note that, because of the selective nature of the secondary compression stage, the overall Lempel-Ziv-Huffman compression process is not equivalent to a Lempel-Ziv compression followed by a standard Huffman encoding. Consequently, the decompression process is not equivalent to a standard Huffman decoding followed by a Lempel-Ziv decompression. The selective use of Huffman encoding with Lempel-Ziv improves the compression ratio but complicates the decompression process and lowers the currently-attainable decompression performance.
The well-known Huffman encoding algorithm achieves compression by assigning short codes to statistically-common symbols, while assigning longer codes to statistically-uncommon symbols. The term “symbol” herein denotes a primitive data element, usually represented by a specified series of bit values. As non-limiting examples, bytes and alphanumeric ASCII characters can be considered to be symbols. The compression of Huffman results directly from the use of variable-length encoding.
“Static Huffman” encoding (which is also referred to in the art as “Fixed Huffman” encoding) utilizes a predetermined fixed encoding scheme and requires a single pass through the data, in which the encoding is done according to the predetermined fixed encoding scheme. “Dynamic Huffman” utilizes an encoding scheme that depends on the statistics of the data being encoded and requires a double pass through the data. The first pass of Dynamic Huffman encoding collects statistical information, from which the encoding tables are venerated, and the second pass performs the encoding according to those encoding tables. Static Huffman encoding is usually employed only for short blocks of data, where it would be counterproductive to use Dynamic Huffman encoding, which requires writing information necessary to reconstruct the encoding tables into the compressed data blocks. For large blocks of data, Dynamic Huffman encoding generally achieves a better compression ratio and is preferred over Static Huffman encoding.
For many applications of lossless compression, a tradeoff involving reduced performance to attain higher compression ratios, is acceptable. For example, a common use of lossless data compression is in data communications, such as for transmitting data over a network. The higher the compression ratio, the lower will be the communication overhead, which usually justifies additional compression/decompression processing because communication costs are always much higher than local processing costs. Lempel-Ziv-Huffman is utilized extensively for lossless data compression in such applications. Well-known data compression/decompression software such as WinZip and PKZip and the Zlib compression/decompression library are widely used to implement Lempel-Ziv-Huffman lossless compression with generally-acceptable performance to achieve good compression ratios for a broad spectrum of data classifications. It is emphasized that in these implementations, Dynamic Huffman encoding (as described above) is normally utilized, because Static Huffman encoding does not attain as good a compression ratio.
Not all applications, however, can justify increased processing overhead when decompressing compressed data. In a non-limiting example, FIG. 1A illustrates functional blocks of a data processing device 100 that utilizes a memory (or storage device) 104 for primary mass storage. Memory 104 can, for example, be a flash memory. Devices of this sort include, but are not limited to, cellular telephones and embedded systems. Device 100 includes a memory controller 102, a CPU 108, and a CPU RAM 110. In the case where memory 104 is too slow to support efficient program execution by CPU 108 (such as in the case of flash memory), software stored in memory 104 must be first loaded from memory 104 into CPU RAM 110 before execution. As illustrated for this example in FIG. 1A, data 106 stored in memory 104 has been previously compressed, to improve efficacy of storage. Thus, compressed data 106 must be decompressed before storage in CPU RAM 110 as decompressed data 112, for direct access and use by CPU 108. Lempel-Ziv-Huffman compression using Dynamic Huffman encoding achieves good compression ratios with reasonable performance, and would be highly desirable for use in such an application. Unfortunately, however, the complexity of Lempel-Ziv-Huffman decompression with Dynamic Huffman decoding currently requires a software implementation for practical applications, and software cannot decompress the data at sufficient speed for fast loading of compressed data from flash memory into CPU RAM. Thus, although a good compression ratio can be attained by using Lempel-Ziv-Huffman compression using Dynamic Huffman encoding, the decompression performance is too low, thereby rendering Lempel-Ziv-Huffman compression using Dynamic Huffman encoding currently unsatisfactory for this and certain other important applications.
A prior art implementation of a system utilizing Lempel-Ziv-Huffman compression and decompression is disclosed in U.S. Pat. No. 5,532,694 to Mayers et al. (herein referred to as “Mayers”). Implementations of Mayers are, in practice, limited to using Static Huffman encoding, although Mayers states that the technique could be further adapted to utilize a Dynamic Huffman scheme.
It is noted that Mayers and other prior art implementations are concerned not only with decompression, but also with compressing the data. This imposes unnecessary limitations on prior art solutions, because in certain applications of data decompression, it may not be necessary for the compression to be performed by the same system or device that does the decompression. As a non-limiting example of this, system 100 (FIG. 1A) has the task of repeatedly decompressing compressed data 106 for execution by CPU 108 In many flash memory applications, compressed data 106 is an executable program or fixed operational data which can be loaded into flash memory 104 already in compressed format. In such cases, system 100 does not need to perform any data compression, but is responsible only for data decompression. It is possible, therefore, to configure such a system to optimize the data decompression performance separately from optimizing the data compression ratio. It is further noted that not only flash memory systems can benefit from such an optimization, but other types of memory and data storage can also benefit therefrom. Hence, the terms “memory”, “memory device”, and “data storage” herein denote any means for storing and retrieving machine-readable data, including, but not limited to: flash memory; RAM; ROM; PROM; register memory and data storage media such as magnetic and optical storage. Neither Mayers nor other prior art provides a means of separately optimizing lossless data compression and lossless data decompression in applications where compressed data stored in data storage or memory, such as flash memory, must be efficiently decompressed for loading into executable memory.
There is thus a need for, and it would be highly advantageous to have, a system and method for improving and optimizing lossless decompression performance for data stored in flash memory or other memory separate from optimizing lossless data compression ratio. In particular, there is a need for a system and method for improving and optimizing decompression performance for data which has been compressed by Lempel-Ziv-Huffman, using Dynamic Huffman encoding and decoding, which is suitable for practical applications such as in flash memory or other memory. The present invention achieves these goals.